var Solution = (grid) => {
  // dp[i][j]表示从左下角到达i,j位置的最小路径和
  // dp[0][0] = grid[0][0]
  // i>0,j=0，在第一列，说明一定是从上一个元素往下移动的才能保证j=0，dp[i][0] = dp[i-1][0]+grid[i][0]
  // i=0,j>0. 在第一列，说明一定是上一个元素向右移动的，dp[0][j] = dp[0][j-1]+grid[0][j]
  // i>0,j>0, 在中间的位置，dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
  var dp = []
  let m = grid.length
  let n = grid[0].length
  for (var i = 0; i < m; i++) {
    dp[i] = []
    for (var j = 0; j < n; j++) {
      if (i == 0 && j == 0) {
        dp[0][0] = grid[0][0]
      } else if (i == 0 && j > 0) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
      } else if (i > 0 && j == 0) {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
      } else if (i > 0 && j > 0) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
      }
    }
  }
  return dp[m - 1][n - 1]
}
console.log(Solution([[1, 3, 1], [1, 5, 1], [4, 2, 1]]));